package com.yuren.codecrushlearn.Q5200;

import com.yuren.codecrushlearn.entities.TreeNode;

/**
 * Created with Intellij IDEA.
 * Description:
 * Bruce Force算法
 * @author 10204
 * @date 2025-05-06 23:51
 */
public class Q5273 {
    private TreeNode root;

    public Q5273() {
        this.root = null;
    }

    public void insert(int value) {
        root = insertRec(root, value);

    }

    private TreeNode insertRec(TreeNode root, int value) {
        if (root == null) {// 该节点上无数据，说明找到对应的位置
            root = new TreeNode(value);
            return root;
        }
        // BST的一个关键性质是，对于任意节点，其左子树中所有节点的值都小于该节点的值，右子树中所有节点的值都大于该节点的值。如果允许重复值，这一性质会被破坏。
        if (root.val == value) {
            return root;
        }
        if (value < root.val) {//value值较小，去左子树找位置
            root.left = insertRec(root.left, value);
        }
        if (value > root.val) {//value值较大，去右子树找位置
            root.right = insertRec(root.right, value);
        }

        return root;
    }

    public TreeNode search(int value) {
        return searchRec(value, this.root);
    }

    private TreeNode searchRec(int value, TreeNode root) {
        if (root == null) {//空节点，找不到
            return null;
        }

        if (value < root.val) {//value值更小，查左子树
            return searchRec(value, root.left);
        }
        if (value > root.val) {//value值更大，查右子树
            return searchRec(value, root.right);
        }

        return root;//相等，返回当前节点
    }
}
